package com.zp.self.module.level_4_算法练习.算法.排序;

import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;

/**
 * @author By ZengPeng
 * 鸣谢：正月点灯笼
 * 参考：https://www.bilibili.com/video/BV1Eb41147dK?spm_id_from=333.337.search-card.all.click
 */
public class VII_堆排序_O_nXlogn {
    @Test
    public void main() {
        int[] orderly = {3,3,4,5,6,6,9,9,12};
        int[] arr = {5, 3, 4, 6, 3, 9, 12, 9, 6};
        for (int i = 0; i < 100; i++) {//打乱100次，验证排序的正确性
            猴子排序_量子级别.shuffle(arr);
            heapSort(arr);
            Assert.assertEquals(Arrays.toString(orderly),Arrays.toString(arr));
        }
        arr =new int[] {1, 342, 232, 22,33, 67, 18, 6765, 2323,34,32,423,432,4,34,34,3,5,46,5,6,2,32,432,5,6,546,45,234,234};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
    题目：堆排序：时间：O(n*logn) 、空间：O(1)、顺序不稳定


    分析：
        堆的定义：
                1.完全二叉树：子节点位置连续
                2.最大堆：父节点大于子节点   ,最小堆：父节点小于子节点
        堆转数组：
                1.由于是完全二叉树，从上往下，从左往右。可以通过计数得到父节点、两个子节点
                2.parent = (i-1)/2  ,C1 = 2i+1 、C2 = 2i+2  ,i的范围【0,length-1】
                3.heapify(arr,index,length)局部堆构建: 比较 parent、C1、C2,将最大值交换给parent。
                  并【递归】 heapify(被交换的节点)，这里一定要递归，因为交换后，子节点可能已经不满足堆的性质了
                  注意：heapify只用比较树的高度那么多的节点，时间复杂度：O(logn)
        实现：
                1.初始化最大堆： 找到最后一个父节点： parent= (n-1)/2  ,parent--;heapify(parent)将整棵树构建成为堆
                2.排序:将对顶的最大值与堆尾做交换，然后调用heapify(arr,index,length)局部堆构建
        时间分析：
                堆排序比冒泡快，因为每拿出最大值后heapify只用比较树的高度那么多的节点，是O(n*log(n))，所以比冒泡的O(n^2)快

     **/
    public void heapSort(int[] nums) {
        //1.初始化最大堆： 找到最后一个父节点 parent,不断的parent--;并构建局部堆
        buildHeap(nums);//遍历了n/2个父节点节点，且每个父节点都做了递归heapify  -- 时间O(n*logn)
        // 2.排序:将对顶的最大值与堆尾做交换，然后调用heapify(对顶)
        for (int index = nums.length-1; index >0; index--) {//时间复杂度：O(n)
            swap(nums,0,index);
            heapify(nums,0,index-1);//时间复杂度：heapify只用比较树的高度那么多的节点 -- 时间复杂度：O(logn)
        }
        //故整体时间复杂度 = n/2 * log(n)  +  n * log(n) = 3n/2 * logn ;忽略常数项, 即：O(n*logn)
    }

    /**
     * Description: 1.初始化最大堆： 找到最后一个父节点 parent,不断的parent--;并构建局部堆
     */
    private void buildHeap(int[] nums) {
        int maxIndex = nums.length-1;
        //找到最大节点，向前遍历，对每个父节点做递归heapify
        for (int index = (maxIndex-1)>>1; index >=0 ; index--) {
           heapify(nums,index,maxIndex);
        }
    }
    /**
     * Description: heapify(arr,index,length)局部堆构建: 比较 parent、C1、C2,将最大值交换给parent。
     *              并【递归】 heapify(被交换的节点)，这里一定要递归，因为交换后，子节点可能已经不满足堆的性质了
     *  maxIndex：我这里用的是最大下标，而不是数组长度了
     */
    private void heapify(int[] nums, int index, int maxIndex) {
        int c1 = 2*index+1;
        int c2 = 2*index+2;
        int max = index;
        if(c1<=maxIndex && nums[c1]>nums[max])
            max = c1;
        if(c2<=maxIndex && nums[c2]>nums[max])
            max = c2;
        if(max!=index){
            swap(nums, index, max);
            heapify(nums,max,maxIndex);
        }
    }
    //交换对象
    private void swap(int[] nums, int index, int max) {
        nums[max] = nums[max]^nums[index];
        nums[index] = nums[max]^nums[index];
        nums[max] = nums[max]^nums[index];
    }
}
